# 导入系统库
from pythonds.trees import BinaryTree
from pythonds.basic import Stack
def buildParseTree(fpexp):
    fplist=fpexp.split()
    pStack=Stack()
    eTree=BinaryTree('')
    pStack.push(eTree)
    currentTree=eTree
    for i in fplist:
        if i=='(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree=currentTree.getLeftChild()
        elif i not in '+-*/)':
            currentTree.setRootVal(eval(i))
            parent=pStack.pop()
            currentTree=parent
        elif i in '+-*/':
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree=currentTree.getRightChild()
        elif i== ')':
            currentTree=pStack.pop()
        else:
            raise ValueError("Unknown Operator:"+i)
    return eTree

# 前序遍历
def preorderTraversal(root) :
    # 保存结果
    result = []

    def traversal(root):
        if root == None:
            return
        result.append(root.key)  # 前序
        traversal(root.leftChild)  # 左
        traversal(root.rightChild)  # 右

    traversal(root)
    return result
# 中序遍历
def inorderTraversal( root) :
    result = []

    def traversal(root):
        if root == None:
            return
        traversal(root.leftChild)  # 左
        result.append(root.key)  # 中序
        traversal(root.rightChild)  # 右

    traversal(root)
    return result

t=BinaryTree('A')
t.insertLeft("B")
l=t.getLeftChild()
l.insertLeft("D")
l.insertRight("E")
l_r=l.getRightChild()
l_r.insertLeft("J")

t.insertRight("C")
r=t.getRightChild()
r.insertLeft("G")
r.insertRight("H")
print(preorderTraversal(t))
print(inorderTraversal(t))
